1. Field of the Invention
This invention relates to a digital processor which is adapted to execute programs employing abstracted applicative language code, and more particularly to such a processor which reduces higher order functions by progressive substitutions of equivalent expressions.
2. Description of the Prior Art
Most digital computers on the market today are still of the type first postulated by John von Neumann and are sequential in their execution of commands. In programming such computers, the programmer has the responsibility for specifying storage management as well as control-flow management and the design of the algorithm to be implemented by the computer. The first higher level languages for programming computers were imperative in nature in that they called for a sequence of commands to be implemented in an iterative fashion. A particular attempt at introducing parallelism into a program execution has been in the creation of data-flow or data-driven systems. See, for example, Barton et al U.S. Pat. No. 3,978,452. However, such systems were still designed to execute programs written in imperative languages which do not readily accommodate a high degree of parallelism.
Pure applicative program languages, such as pure LISP, differ from the more conventional imperative languages, such as FORTRAN and COBOL, in that the latter specify a sequence of steps to be carried out in a particular order while the former do not. Applicative languages generally are based on the lambda calculus of A. Church and are very concise. However, they do not provide for storage and are not history sensitive. Thus, practical implementations of such languages as LISP take on may iterative features and the programmer is still responsible for control-flow sequencing as well as the basic algorithm design (cf., J. McCarthy et al, LISP 1.5 Programmers' Manual, M.I.T. Press, 1962).
A particular applicative language as a readable alternative to pure LISP is the Saint Andrews Static Language, or SASL, which was proposed by David A. Turner (SASL Language Manual, University of St. Andrews, 1976). This language can be implemented by employing a number of "combinators" and also primitive functions to transform SASL source code into a notation in which bound variables do not occur to produce a variable-free object code, (D. A. Turner, "A New Implementation Technique for Applicative Languages", Software--Practice and Experience, Vol. 9, pp. 31-49, 1979). This language is particularly advantageous for handling higher order functions, including nested functions and non-strict functions in which an answer may be returned even though one of its arguments is undefined. Thus, when a particular combinator is encountered, it can be reduced or evaluated by progressive substitutions of equivalent expressions. As a result, two-cell nodes may be stored in memory as a treelike graph where some cells specify either a function such as a combinator or a primitive function and other cells specify a value or pointers or addresses to other cells. A node may contain both a function and a value.
Such programs may be said to be demand-driven in that only those functions are evaluated as are necessary and the language is completely concurrent in that the respective functions can be evaluated independently of one another subject to the constraint that, for a given graph, some functions may terminate and others may not. Thus, such programs may be executed by a network of reduction processors operating either simultaneously or independently of one another. In this manner the programmer is relieved of both storage management responsibilities as well as the responsibilities for the control-flow management.
It is, then, an object of the present invention to provide an improved digital processor in which storage management and control-flow management are automatic.
It is another object of the present invention to provide an improved digital processor for executing applicative-type language codes from which bound variables have been removed.
Still a further object of the present invention is to provide an improved digital processor for reduction of higher order functions stored in memory as treelike graphs.